你知道 Iterable 有多慢吗？试试它提升性能
hi 这是 dhl 的第 67 篇原创文章个人微信: hi-dhl
Hi 大家好，我是 DHL。公众号：ByteCode ，专注分享有趣硬核原创内容，Kotlin、Jetpack、性能优化、系统源码、算法及数据结构、动画、大厂面经。
关于 Sequence 我在之前的两篇文章都介绍过，无论在执行速度和内存方面 Sequence 的性能都比 Iterable 好，有兴趣的朋友可以去看一下：
在上一篇文章中测试了反射的性能 揭秘反射真的很耗时吗，射10万次用时多久，这篇文章我们一起来分析一下 Sequence 和 Iterable 的执行过程和性能。这期内容分为 视频版 和文字版，仅仅靠文字无法很好的描述它们的执行过程。
视频版以动画的形式描述了 Sequence 和 Iterable 的执行过程和性能测试过程，视频还在制作中，后面会在 bilibili 和视频号上发布，欢迎关注我，获取最新内容。
这期内容将会从 速度 和 内存 两方面测试一下它们之间的差距。我们先来看一看 Sequences 和 Iterable 数据结构，它们的数据结构非常的相似。
Sequences 和 Iterable 虽然结构很相似，但是他们的性能缺相差很大，在开始测试之前，我们先来看看它们的执行过程。
Iterable 的执行过程
Iterable 会立即处理输入的元素，在处理过程中，每遇到一个操作符，都会创建一个新的数组列表，将结果保存到新的数组列表中，之后在传递给下一个操作符，以此类推，直到操作符结束，我们来看一段代码。
.map { it * 2 }
.filter { it > 2 }
.forEach { print("$it, ") }
Iterable 执行过程如下图所示。
初始集合所有元素
1, 2, 3，遇到第一个操作符map，会创建一个新的数组列表，遍历初始集合所有元素，每个元素 x 2 保存到新的数组列表中，输出2, 4, 6，源码如下所示
public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}
然后调用第二个操作符
filter，会再次创建一个新的数组列表，遍历集合中所有元素，将大于 2 的元素，保存到新的数组列表中，输出4, 6，源码如下所示
public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
return filterTo(ArrayList<T>(), predicate)
}
如果每次调用操作符 map 、 filter 时，都创建一个新的数组列表，将结果保存到新的数组列表中。这么做存在性能问题。
1. 浪费内存
每次调用操作符 map 、 filter 时，都需要临时申请一段内存存储中间结果。
如果每次操作都需要申请内存，存储中间结果，这是对内存极大的浪费，因为我们只关心最后的结果，而不是中间的过程。
2. 执行速度慢
每次调用操作符 map 、 filter 时，都会生成一个 while{...} 循环, 原本只需要遍历一次就能做完的事，被拆分多个循环来完成，如果在大量数据的情况下，这个速度是很糟糕的。
Sequences 的执行过程
Sequence 用来表示一个延迟计算的集合，每次遇到一个中间操作符都不会执行，会把它添加到待执行的操作列表中，构成一个待执行的调用链，直到遇到终端操作符（ toList 、 count 、 forEach 等等）才会开始执行。
我们可以通过 asSequence 扩展函数，将现有的集合转换为 Sequence ，示例代码如下所示。
.map { it * 2 }
.filter { it > 2 }
.forEach { print("$it, ") }
Sequence 执行过程如下图所示。
初始集合所有元素
1，2，3，调用asSequence扩展函数，将现有的集合转换为Sequence遇到第一个操作符
map，map是中间操作符，不会执行，会把它添加到待执行的操作列表中然后调用第二个操作符
filter，filter也是一个中间操作符，也会把它添加到待执行的操作列表中。调用最后一个操作符
forEach，forEach是终端操作符，遇到终端操作符时，会触发中间操作符的执行，初始集合每个元素都会执行一遍map -> filter -> forEach，直到所有元素处理完毕
在 Sequences 处理过程中，遇到中间操作符 map 、 filter 不会执行，只是构建了一个待执行的调用链，只有遇到末端操作符 forEach 才开始处理元素，这么做有以下好处：
速度更快，将多个中间操作符，构成一个待执行的调用链，集合中每个元素在调用链上传递，避免了很多无用操作，提升了整体速度
占用更少的内存，在执行过程中，不会创建新的列表存储中间结果，因此它占用的内存更少
如何区分末端操作符还是中间操作符
看方法的返回类型，如果返回的是 Sequence 表示是中间操作符，否则是终端操作符，源码如下所示。
public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R> {
return TransformingSequence(this, transform)
}
// 末端操作 toList 返回的是一个具体的类型（List）
public fun <T> Sequence<T>.toList(): List<T> {
return this.toMutableList().optimizeReadOnlyList()
}
如果是中间操作 map 、 filter ，它们返回的是一个 Sequence，末端操作返回的是一个具体的类型 List 、 Int 、 Unit 等等，源码如下所示。
public fun <T> Sequence<T>.count(): Int {
var count = 0
for (element in this) checkCountOverflow(++count)
return count
}
// 末端操作 forEach 返回的是一个具体的类型（Unit）
public inline fun <T> Sequence<T>.forEach(action: (T) -> Unit): Unit {
for (element in this) action(element)
}
如果是末端操作符 toList 、 count 、 forEach 等等，返回的是一个具体的类型 List 、 Int 、 Unit。
了解完 Sequences 和 Iterable 的执行过程，接下里我们实操一下，通过 JMH 工具测试一下它们的执行速度，通过 jcmd 生成 hprof 文件查看它们的总内存。
JMH (Java Microbenchmark Harness)，这是 Oracle 开发的一个基准测试工具，因为 JVM 会对代码做各种优化，而 JMH 会尽可能的减少这些优化对最终结果的影响，尽可能的保证结果的可靠性。
代码已经上传到 Github 仓库 KtPractice 欢迎前往查看，运行 SequenceBenchmark 和 TestSequenceMemory 即可生成结果。
Github 仓库 KtPractice 地址：https://github.com/hi-dhl/KtPractice
Sequences 和 Iterable 执行速度对比
在开始测试之前，我们需要先设计测试方案：
在单进程，10 个线程中，分别对
Sequences和Iterable执行 10 轮测试，每轮遍历 10 万条数据，取平均值在执行之前，需要对代码进行预热，预热不会作为最终结果，预热的目的是为了构造一个相对稳定的环境，保证结果的可靠性。因为 JVM 会对执行频繁的代码，尝试编译为机器码，从而提高执行速度。而预热不仅包含编译为机器码，还包含 JVM 各种优化算法，尽量减少 JVM 的优化，构造一个相对稳定的环境，降低对结果造成的影响。
JMH 提供 Blackhole，通过 Blackhole 的 consume 来避免 JIT 带来的优化
现在分别使用 Sequences 和 Iterable 调用它们各自的 filter 、 map 方法，处理相同数据的情况下，比较它们的执行时间。
Iterable
@Benchmarkfun runIterable(bh: Blackhole) {
val result = (1..100_000).asIterable()
.map { it * 2 }
.filter { it % 2 == 1 }
.count()
bh.consume(result)
}
处理完 10 万条数据之后，10 轮测试平均耗时 10.259 ms/op 。
Sequences
@Benchmarkfun runSequence(bh: Blackhole) {
val result = (1..100_000).asSequence()
.map { it * 2 }
.filter { it % 2 == 1 }
.count()
bh.consume(result)
}
经过长时间运行之后，10 轮测试平均耗时 4.914 ms/op ，这个结果很让人吃惊，Sequences 比 Iterable 快 6 倍。如下图所示：
在实际情况中，集合里面保存的元素更加复杂，因此占用内存、和执行速度之间的差距也会越来越大。尤其在处理大数据的时候，效果是更加明显的，数据量越大，它们的时间差距会越来越大。
Sequences 和 Iterable 内存对比
在开始测试之前，我们需要先设计测试方案：
分别使用
Sequences和Iterable，创建 10 万个对象，查看当前内存情况利用 JDK 提供的工具
jcmd在循环结束后，方法结束前，生成hprof文件，查看当前总内存大小需要一个简单的测试类，作为
Sequences和Iterable测试数据，测试类如下所示
private var name: String? = null
private var addres: String? = null
private var age: Int = 0
}
现在分别使用 Sequences 和 Iterable 调用它们各自的 filter 、 map 方法，来看看它们的内存占用情况。
Iterable
(1..100_000).asIterable().map { Model(it) }
.filter { it.no > 1000 }
.count()
val pid = getProcessID()
val millis = System.currentTimeMillis()
val process = Runtime.getRuntime().exec("jcmd ${pid} GC.heap_dump report/sequence/memory_iterables_${pid}_${millis}.hprof")
println(process.waitFor())
创建 10 万个对象之后，在方法执行结束前，生成 hprof 文件，分析之后，总共占用 6 MB (6, 046, 244 byte) 内存。
Sequences
(1..100_000).asSequence().map { Model(it) }
.filter { it.no > 1000 }
.count()
val pid = getProcessID()
val millis = System.currentTimeMillis()
val process = Runtime.getRuntime().exec("jcmd ${pid} GC.heap_dump memory_sequences_${pid}_${millis}.hprof")
println(process.waitFor())
总共占用 1 MB (1, 495, 413 byte) 内存，最终 Sequences 和 Iterable 内存占用情况如下所示。
这个结果非常的惊人， Iterable 占用的内存是 Sequences 6 倍，这是因为 Iterable 每次遇到一个操作符，都会创建一个新的数组列表，将结果保存到新的数组列表中，导致了浪费更多的内存
Iterable 和 Sequences 如何选择
经过速度和内存测试，我们知道了使用 Sequences 不仅可以提高速度，而且占用的内存更少。那么如何选择 Iterable 和 Sequences。
如果包含多个操作符，建议选择
Sequences在数据量很小的情况下，选择任意一个都可以，但是如果是在递归当中使用，无论数据大小，建议优先考虑
Sequences如果处理的数据量比较大，
Sequence是最好的选择，因为不会创建新的数组列表，内存开销更小，而且速度更快如果单个 Model 非常的复杂，无论数据集大小，建议优先考虑
Sequences，如果无法确定，那么在想使用Iterable的时候，优先考虑Sequences
本文代码已经全部上传到 Github 仓库 KtPractice 欢迎前往查看，运行 SequenceBenchmark 和 TestSequenceMemory 即可生成结果，或者进入仓库 report/sequence 目录下查我已经生成好的结果。
Github 仓库 KtPractice 地址：https://github.com/hi-dhl/KtPractice
全文到这里就结束了，如果对你有帮助，欢迎 在看、点赞、收藏、分享 给身边的朋友。
推荐阅读：
Stack Overflow 上最热门的 10 个 Kotlin 问题？
公众号：ByteCode ，分享有用、有趣的硬核原创内容，Kotlin、Jetpack、性能优化、系统源码、算法及数据结构、动画、大厂面经。
👇🏻 真诚推荐你关注我👇🏻
因微信公众号更改了推送机制
可能无法及时看到最新文章
将公众号设为 星标
或常为文章点 在看
即可及时收到最新文章
欢迎前往 博客 查看更多 Kotlin、Jetpack 、动画算法图解、系统源码分析等等文章。以及开源项目、LeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解。
https://www.hi-dhl.com